Abstract: The related work deals with the fast nearest string search in large spatial databases. Specifically, it investigates spatial range queries extent with a string similarity nearest search predicate in both Euclidean distance and road networks.. The spatial approximate string (SAS) query search problem is common in searching the approximate string in large spatial database. To apply the range queries augmented with a string similarity search predicate in both Euclidean space and road networks. In Euclidean space, we propose an approximate solution, the MHR-tree, which fix min-wise signatures into an R-tree. The min-wise signature for an index node keeps a pithy representation of the union of q -grams from strings under the sub tree of u. We analyze the cut away functionality of such signatures based on the set resemblance between the query string and the q -grams from the sub trees of index nodes. We also discuss how to estimate the selectivity of a SAS query in Euclidean space, for which we present a novel adaptive algorithm to find balanced partitions using both the spatial and string information stored in the tree. For queries on road networks, we propose a more exact method, The RSASSOL algorithm partitions the road network, adaptively searches relevant sub graphs, and prune candidate points using two attributes reference nodes and index of string matching. Lastly, an adapted Multipoint algorithm (MPALT) is applied, together with the exact edit distances, to verify the final set of candidates.

Keywords: Approximate string, Spatial database, RSASSOL, MPALT, Road network.